Section: New Results

Code-based cryptography

Participants : Rodolfo Canto Torres, Julia Chaulet, André Chailloux, Thomas Debris, Adrien Hauteville, Nicolas Sendrier, Jean-Pierre Tillich, Matthieu Lequesne, Valentin Vasseur, Matthieu Vieira.

The first cryptosystem based on error-correcting codes was a public-key encryption scheme proposed by McEliece in 1978; a dual variant was proposed in 1986 by Niederreiter. We proposed the first (and only) digital signature scheme in 2001. Those systems enjoy very interesting features (fast encryption/decryption, short signature, good security reduction) but also have their drawbacks (large public key, encryption overhead, expensive signature generation). Some of the main issues in this field are

• security analysis, including against a quantum adversary, implementation and practicality of existing solutions,

• reducing the key size, e.g., by using rank metric instead of Hamming metric, or by using structured codes,

• addressing new functionalities, like identity-based encryption, hashing or symmetric encryption.

As mentioned in Section 5.1.1, the NIST is currently running a standardization effort for quantum-safe cryptography, where code based cryptography is a promising technique.

Our work in this area can be decomposed as follows:

• suggesting code-based solutions to the NIST competition;

• cryptanalyzing code-based schemes;

• fundamental work on code-based cryptography.

Code-based solutions to the NIST competition

We have proposed two key-exchange protocols to the NIST competition:

• the first one [67] is based on quasi-cyclic MDPC codes and the work [40];

• the second one [69] is based on quasi-cyclic Goppa codes.

Both of them are able to reduce significantly the keysizes by relying on quasi-cyclic codes.

Cryptanalysis of code-based cryptography

Here our work can be summarized as follows:

• cryptanalysis of McEliece schemes based on wild Goppa codes over quadratic extension fields [24];

• improving generic attacks on rank metric codes [68];

• side-channel attacks on quasi-cyclic MDPC bit flipping decoder [74].

Fundamental work on code-based cryptography

• studying precisely the complexity of statistical decoding techniques [71], [48];

• suggesting the first code-based identity-based encryption by using rank metric codes [49];

• suggesting a code-based signature scheme [43];

• analysing and improving the decoding of quasi-cyclic MDPC codes [12], [78];

• studying families of codes that might be used in a cryptographic setting [53].

• improving the complexity of quantum decoding algorithms [50];

• studying [70], [56], [30] whether security reductions for signature schemes are quantum safe when considering the quantum random oracle model (QROM). We were particularly interested in code-based Full Domain Hash constructions. We show that if the underlying correcting code we use has good pseudo random properties then it is possible to perform a quantum security reduction in the QROM.